package Hash;

import java.util.HashMap;
import java.util.Map;

//四数相加
public class sum4_ii {
    /*
    * 给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：
        0 <= i, j, k, l < n
        nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
        * 示例 1：
输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出：2
解释：
两个元组如下：
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0*/

    /**
     *题目解析：
     * 1.给了四个数组，然后问有多少种组合(i,j,k,l) 让nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
     * 返回组合数量
     */
    /**
     *在处理相加/相减问题中，注意： 比如有四个数 n1，n2，n3，n4,；n1和n2去组合后，再和n3、n4去组合，结果和n1、n2、n3、n4组合的结果是一样的，但是第一种的复杂度低
     * 第一种的时间复杂度是n^2，第二种是n^3，当然，也可以是n1，然后n2，n3，n4去组合，但这种的时间复杂度是n^3,不如两两组合
     */
    //先计算组合1和组合2，再去利用value相乘
    public static int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        //这里的key保存相加的结果，value保存出现的次数，因为key不能重复
        HashMap<Integer,Integer> map12=new HashMap<>();
        HashMap<Integer,Integer> map34=new HashMap<>();
        //四个数组的长度是一样的
        //这里去遍历nums1和nums2的组合，去得到他们的相加之后的结果
        for (int i = 0; i < nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {
                int sum12=nums1[i]+nums2[j];
                //判断是否出现过
                //这里去得到数组1、2的结果
                map12.put(sum12, map12.getOrDefault(sum12,0)+1);
                //todo:1.如果这里采用先去计算map34，这里去得到0-数组3、4的结果，因为这里要根据这个得出的结果去map12找
                int sum34=0-(nums3[i]+nums4[j]);
                map34.put(sum34, map34.getOrDefault(sum34,0)+1);
            }
        }
        //遍历map12，去寻找map34有没有对应的【因为map34是利用0-得来的】
        int count=0;
        for (Map.Entry<Integer, Integer> index : map12.entrySet()) {
            if(map34.containsKey(index.getKey())){
                //todo:2.那么这里应该利用index.getValue()*map34.get(index.getKey()) 因为得利用map12和map34的结果
                //比如：map12中有0的个数是2，map34中0个value也是2，那么最终的组合就是4，而不是2，所以这里得利用两个的value*
                //todo:注意这里不是index.getValue()*map34.get(index.getKey())，组合嘛，肯定是用*
                count=count+index.getValue()*map34.get(index.getKey());
            }
        }
        return count;
    }
    //先计算组合1，再在组合3的过程中加上12的value
    public static int fourSumCount_2(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        //这里的key保存相加的结果，value保存出现的次数，因为key不能重复
        HashMap<Integer,Integer> map12=new HashMap<>();
        HashMap<Integer,Integer> map34=new HashMap<>();
        //四个数组的长度是一样的
        //这里去遍历nums1和nums2的组合，去得到他们的相加之后的结果
        for (int i = 0; i < nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {
                int sum12=nums1[i]+nums2[j];
                //判断是否出现过
                //这里去得到数组1、2的结果
                map12.put(sum12, map12.getOrDefault(sum12,0)+1);
            }
        }
        int count=0;
        //因为上面没有顺便计算map34的组合，下面计算，在计算时，顺便把对应的计数加上去了
        //比如：现在已知的是map12的0是2
        //然后这里：在遍历时，从num34中得到结果0，那么就去寻找map12中是否有结果为0的，如果有，则去+1，然后第二次从num34中得到0，再去寻找map12中结果为0的，再加上该次数，从而达到相乘的结果！
        for (int i = 0; i < nums3.length; i++) {
            for (int j = 0; j < nums4.length; j++) {
                int sum=0-nums3[i]-nums4[j];
                count=count+map12.getOrDefault(sum,0);
            }
        }
        return count;
    }

    public static void main(String[] args) {
        fourSumCount(new int[]{-1,-1},new int[]{-1,1},new int[]{-1,1},new int[]{1,-1});
    }
}
